package collectTheCoins;

import java.util.*;

class Solution {
    public int collectTheCoins(int[] coins, int[][] edges) {
        int n = coins.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<Integer>();
        }
        int[] degree = new int[n];
        for (int[] edge : edges) {
            int x = edge[0], y = edge[1];
            g[x].add(y);
            g[y].add(x);
            ++degree[x];
            ++degree[y];
        }

        int rest = n;
        /* 删除树中所有无金币的叶子节点，直到树中所有的叶子节点都是含有金币的 */
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1 && coins[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int u = queue.poll();
            --degree[u];
            --rest;
            for (int v : g[u]) {
                --degree[v];
                if (degree[v] == 1 && coins[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        /* 删除树中所有的叶子节点, 连续删除2次 */
        for (int x = 0; x < 2; ++x) {
            queue = new ArrayDeque<Integer>();
            for (int i = 0; i < n; ++i) {
                if (degree[i] == 1) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                int u = queue.poll();
                --degree[u];
                --rest;
                for (int v : g[u]) {
                    --degree[v];
                }
            }
        }

        return rest == 0 ? 0 : (rest - 1) * 2;
    }
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 拓扑排序
        // 每次删掉入度为0的点
        // 建图
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<>();
        }
        int[] indegree = new int[numCourses];
        for (int[] pre: prerequisites) {
            g[pre[1]].add(pre[0]);
            indegree[pre[0]]++;
        }
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < numCourses; i++) {
            if(indegree[i] == 0) {
                stack.push(i);
            }
        }
        List<Integer> ans = new ArrayList<>();
        while (!stack.isEmpty()) {
            int course = stack.pop();
            for (int v: g[course]) {
                indegree[v]--;
                if(indegree[v]==0){
                    stack.add(v);
                }
            }
            ans.add(course);
        }
        return ans.size() == numCourses;
    }
    public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
        // 交换糖果
        int alice = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < aliceSizes.length; i++) {
            set.add(aliceSizes[i]);
            alice+=aliceSizes[i];
        }
        int bob = Arrays.stream(bobSizes).sum();
        int target = (alice+bob)/2;
        for (int i = 0; i < bobSizes.length; i++) {
            // bob - bob[i] + alice[k] == target
            // alice[k] = target-bob+bob[i]
            if(set.contains(target-bob+bobSizes[i])) {
                return new int[]{target-bob+bobSizes[i],bobSizes[i]};
            }
        }
        return null;
    }
    public boolean hasGroupsSizeX(int[] deck) {
        int[] count = new int[10000];
        for (int c: deck) {
            count[c]++;
        }

        int g = -1;
        for (int i = 0; i < 10000; ++i) {
            if (count[i] > 0) {
                if (g == -1) {
                    g = count[i];
                } else {
                    g = gcd(g, count[i]);
                }
            }
        }
        return g >= 2;
    }
    public int gcd(int x, int y) {
        return x == 0 ? y : gcd(y % x, x);
    }
    public int repeatedNTimes(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if(!set.add(nums[i])){
                return nums[i];
            }
        }
        return -1;
    }
    public int findJudge(int n, int[][] trust) {
        //
        int[] cnt = new int[n+1];
        boolean[] bol = new boolean[n+1];
        for (int[] t: trust) {
            cnt[t[1]]++;
            bol[t[0]] = true;
        }
        for (int i = 1; i <= n; i++) {
            if(cnt[i] == n-1&&!bol[i]){
                return i;
            }
        }
        return -1;
    }
    public int maxNumberOfBalloons(String text) {
        // 气球的最大数量
        // 每个字母的需求 balloon
        int b = 0,a = 0,l = 0,o = 0,n =0;
        for (int i = 0; i < text.length(); i++) {
            if(text.charAt(i) == 'b'){
                b++;
            }else if(text.charAt(i) == 'a'){
                a++;
            }else if(text.charAt(i) == 'l'){
                l++;
            }else if(text.charAt(i) == 'o'){
                o++;
            }else if(text.charAt(i) == 'n'){
                n++;
            }
        }
        return Math.min(Math.min(Math.min(b,Math.min(a,o/2)),l/2),n);
    }
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int upper = 0;
        for (int x : arr1) {
            upper = Math.max(upper, x);
        }
        int[] frequency = new int[upper+1];
        for (int v: arr1) {
            ++frequency[v];
        }
        // 统计每个元素出现的次数
        int index = 0;
        for (int v: arr2) {
            while (frequency[v]>0){
                arr1[index++] = v;
                frequency[v]--;
            }
        }
        // 再arr2中没有出现的元素 按照升序排序
        for (int i = 0; i <= upper; i++) {
            while (frequency[i]>0){
                arr1[index++] = i;
                frequency[i]--;
            }
        }
        return arr1;
    }
    public int[] arrayRankTransform(int[] arr) {
        //
        int[] tmp = Arrays.copyOf(arr,arr.length);
        Arrays.sort(tmp);
        Map<Integer,Integer>map = new HashMap<>();
        int t = 1;
        for (int i = 0; i < tmp.length; i++) {
            if(map.containsKey(tmp[i])) {

            } else {
                map.put(tmp[i],t);
                t++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = map.get(arr[i]);
        }
        return arr;
    }
    public boolean checkIfExist(int[] arr) {
        //
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if(set.contains(arr[i]*2)) {
                return true;
            } else if (arr[i]%2==0 && set.contains(arr[i]/2)) {
                return true;
            }
            set.add(arr[i]);
        }
        return false;

        // 双指针
//        Arrays.sort(arr);
//        int l = 0,r = arr.length-1;
//        while (l<r) {
//            if(arr[l]*2<arr[r]) {
//                l++;
//            } else if (arr[l]*2>arr[r]) {
//                r--;
//            } else {
//                return true;
//            }
//        }
//        return false;
    }
    public int[] smallerNumbersThanCurrent(int[] nums) {
        // 差分数组
        // 每次让后面的数字+1
//        int[] cnt = new int[102];
//        for (int i = 0; i < nums.length; i++) {
//            cnt[nums[i]+1]++;
//            cnt[101]--;
//        }
//        for (int i = 1; i < cnt.length; i++) {
//            cnt[i]+=cnt[i-1];
//        }
//        for (int i = 0; i < nums.length; i++) {
//            nums[i] = cnt[nums[i]];
//        }
//        return nums;

        // 计数排序
        int[] cnt = new int[102];
        for (int i = 0; i < nums.length; i++) {
            cnt[nums[i]]++;
        }
        // 求前缀和
        for (int i = 1; i < 102; i++) {
            cnt[i] += cnt[i-1];
        }
        int[] ret = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ret[i] = nums[i] == 0 ? 0 : cnt[nums[i] - 1];
        }
        return ret;
    }
    public String sortString(String s) {
        // 桶排序
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i)-'a']++;
        }
        StringBuilder sb = new StringBuilder();
        while (sb.length()<s.length()) {
            for (int i = 0; i < 26; i++) {
                if(cnt[i] >= 1) {
                    cnt[i]--;
                    sb.append((char) (i+'a'));
                }
            }
            for (int i = 25; i >=0 ; i--) {
                if(cnt[i] >= 1) {
                    cnt[i]--;
                    sb.append((char) (i+'a'));
                }
            }
        }
        return sb.toString();
    }
    public int findLucky(int[] arr) {
        // 出现次数和大小相等
        int[] cnt = new int[501];
        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]]++;
        }
        int ans = -1;
        for (int i = 1; i < 501; i++) {
            if(cnt[i] == i) {
                ans = i;
            }
        }
        return ans;
    }
    public int countLargestGroup(int n) {
        int[] cnt = new int[37];
        int max = 0;
        for (int i = 1; i <= n; i++) {
            int tmp = i;
            int res = 0;
            while (tmp>0) {
                res+=tmp%10;
                tmp/=10;
            }
            cnt[res]++;
            max = Math.max(cnt[res],max);
        }
        int ans = 0;
        for (int i = 0; i < cnt.length; i++) {
            if(cnt[i] == max){
                ans++;
            }
        }
        return ans;
    }
    public String destCity(List<List<String>> paths) {
        Set<String> citiesA = new HashSet<String>();
        for (List<String> path : paths) {
            citiesA.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (!citiesA.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return "";
    }
    public boolean canBeEqual(int[] target, int[] arr) {
        // 任意子数组翻转
        int[] cnt = new int[1001];
        for (int i = 0; i < arr.length; i++) {
            cnt[arr[i]]++;
        }
        for (int i = 0; i < target.length; i++) {
            cnt[target[i]]--;
        }
        for (int i = 0; i < 1001; i++) {
            if(cnt[i]!=0)return false;
        }
        return true;
    }
    public int numIdenticalPairs(int[] nums) {
        // nums[i] == nums[j]
        int ans = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int t = map.getOrDefault(nums[i],0);
            ans+=t;
            map.put(nums[i],t+1);
        }
        return ans;
    }
    public int maxLengthBetweenEqualCharacters(String s) {
        int[] cnt = new int[26];
        Arrays.fill(cnt,-1);
        int ans = -1;
        for (int i = 0; i < s.length(); i++) {
            int c = s.charAt(i)-'a';
            if(cnt[c] != -1) {
                ans = Math.max(ans,i-cnt[c]-1);
            } else {
                cnt[c] = i;
            }
        }
        return ans;
    }
    public int[] frequencySort(int[] nums) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int num : nums) {
            cnt.put(num, cnt.getOrDefault(num, 0) + 1);
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int num : nums) {
            list.add(num);
        }
        Collections.sort(list, (a, b) -> {
            int cnt1 = cnt.get(a), cnt2 = cnt.get(b);
            return cnt1 != cnt2 ? cnt1 - cnt2 : b - a;
        });
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            nums[i] = list.get(i);
        }
        return nums;
    }
    // 快排
    private void quiskSort(int[] nums,Comparator<Integer> comparator){
        quickSort(nums,0,nums.length-1);
    }
    private void quickSort(int[] nums,int l,int r) {
        if(l<r) {
            int pivotPos = parartion(nums,l,r);
            quickSort(nums,l,pivotPos-1);
            quickSort(nums,pivotPos+1,r);
        }
    }
    private int parartion(int[] nums,int l,int r) {
        int pivot = nums[l];
        while (l<r) {
            while (l<r&&nums[r]>=pivot) {
                r--;
            }
            nums[r] = nums[l];
            while (l<r&&nums[l]<=pivot) {
                l++;
            }
            nums[l] = nums[r];
        }
        nums[l] = pivot;
        return l;
    }
    public boolean canFormArray(int[] arr, int[][] pieces) {
        //
        Map<Integer,int[]> map = new HashMap<>();
        for (int i = 0; i < pieces.length; i++) {
            map.put(pieces[i][0],pieces[i]);
        }
        int i = 0;
        while (i<arr.length) {
            int[] tmp = map.getOrDefault(arr[i],null);
            if(tmp == null) {
                return false;
            }
            for (int j = 0; j < tmp.length; j++) {
                if(arr[i+j] != tmp[j]) {
                    return false;
                }
            }
            i+=tmp.length;
        }
        return true;
    }
    public boolean isPathCrossing(String path) {
        // 数对(x,y) --> x*10+y;
        Set<Integer> set = new HashSet<>();
        int x = 0,y = 0;
        set.add(0);
        for (int i = 0; i < path.length(); i++) {
            switch (path.charAt(i)) {
                case 'N' ->{
                    y++;
                }
                case 'S' ->{
                    y--;
                }
                case 'E' ->{
                    x++;
                }
                case 'W' ->{
                    x--;
                }
            }
            int t = x*10000+y;
            if(set.contains(t))return true;
            set.add(t);
        }
        return false;
    }
    class OrderedStream {
        String[] stream;
        private int ptr = 1;
        public OrderedStream(int n) {
            stream = new String[n+1];
        }
        public List<String> insert(int idKey, String value) {
            stream[idKey] = value;
            List<String> res = new ArrayList<String>();
            while (ptr < stream.length && stream[ptr] != null) {
                res.add(stream[ptr]);
                ++ptr;
            }
            return res;
        }
    }
    public int countConsistentStrings(String allowed, String[] words) {
        int mask = 0;
        for (int i = 0; i < allowed.length(); i++) {
            mask|=(1<<allowed.charAt(i)-'a');
        }
        int ans = 0;
        for (String w: words) {
            int mask2 = 0;
            for (int i = 0; i < w.length(); i++) {
                mask2|=1<<(w.charAt(i)-'a');
            }
            if((mask|mask2) == mask) {
                ans++;
            }
        }
        return ans;
    }
    public int sumOfUnique(int[] nums) {
        int[] map = new int[101];
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if(map[nums[i]] == 0) {
                map[nums[i]] = 1;
                ans += nums[i];
            } else if (map[nums[i]] == 1) {
                map[nums[i]] = 2;
                ans -= nums[i];
            }
        }
        return ans;
    }
    public String longestNiceSubstring(String s) {
        // 最长美好字符串
        // 大写和小写同时出现
        String ans = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i+1; j < s.length(); j++) {
                if(j-i+1<=ans.length()) continue;
                int lowr = 0; // 小写
                int upper = 0; // 大写
                // 完全相同 lowr == upper
                String t = s.substring(i,j+1);
                for (int k = 0; k < t.length(); k++) {
                    if(Character.isLowerCase(t.charAt(k))) {
                        lowr|=(1<<(t.charAt(k)-'a'));
                    } else {
                        upper|=(1<<(t.charAt(k)-'A'));
                    }
                }
                if(lowr == upper) {
                    ans = t;
                }
            }
        }
        return ans;
    }
    public int numDifferentIntegers(String word) {
        // 不含前导0的十进制数字相同
        Set<String> set = new HashSet<String>();
        int n = word.length(), p1 = 0, p2;
        while (true) {
            while (p1 < n && !Character.isDigit(word.charAt(p1))) {
                p1++;
            }
            if (p1 == n) {
                break;
            }
            p2 = p1;
            while (p2 < n && Character.isDigit(word.charAt(p2))) {
                p2++;
            }
            while (p2 - p1 > 1 && word.charAt(p1) == '0') { // 去除前导 0
                p1++;
            }
            set.add(word.substring(p1, p2));
            p1 = p2;
        }
        return set.size();
    }
    public int secondHighest(String s) {
        // 第二大的数字
        int max1 = -1;
        int max2 = -1;
        for (int i = 0; i < s.length(); i++) {
            if(s.charAt(i)>='0'&&s.charAt(i)<='9') {
                if(s.charAt(i)-'0'>max1) {
                    max2 = max1;
                    max1 = s.charAt(i) - '0';
                } else if (s.charAt(i)-'0' == max1){

                } else if (s.charAt(i)-'0'>max2) {
                    max2 = s.charAt(i) - '0';
                }
            }
        }
        return max2;
    }
    public boolean areAlmostEqual(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int i = 0;
        int j = 1;
        while (i<s1.length()&&j<s2.length()) {
            if(chars1[i]==chars2[i]){
                i++;
                j = i+1;
            } else if (chars1[j]==chars2[j]) {
                j++;
            } else {
                char c = chars1[i];
                chars1[i] = chars1[j];
                chars1[j] = c;
                break;
            }
        }
        return Arrays.equals(chars1,chars2);
    }
}
